<!DOCTYPE html>
<html lang="zh-CN">
  <head>
    <meta charset="UTF-8" />
    <meta name="viewport" content="width=device-width, initial-scale=1.0" />
    <title>Canvas提示框自动布局系统</title>
    <style>
      body {
        margin: 0;
        display: flex;
        justify-content: center;
        align-items: center;
        height: 100vh;
        background-color: #f0f0f0;
        font-family: Arial, sans-serif;
      }
      .container {
        position: relative;
      }
      canvas {
        border: 1px solid #ccc;
        background-color: white;
      }
      .controls {
        margin-top: 10px;
        display: flex;
        gap: 10px;
        justify-content: center;
      }
      button {
        padding: 8px 16px;
        background-color: #4caf50;
        color: white;
        border: none;
        border-radius: 4px;
        cursor: pointer;
      }
      button:hover {
        background-color: #45a049;
      }
      .stats {
        margin-top: 10px;
        text-align: center;
        font-size: 14px;
      }
    </style>
  </head>
  <body>
    <div class="container">
      <canvas id="canvas" width="800" height="600"></canvas>
      <div class="controls">
        <button id="randomPoints">生成随机点</button>
        <button id="optimizeLayout">优化布局</button>
        <button id="toggleLabels">显示/隐藏标签</button>
      </div>
      <div class="stats">
        <span id="overlapCount">重叠数: 0</span>
        <span id="iterations">迭代次数: 0</span>
      </div>
    </div>

    <script>
      // 获取Canvas元素和绘图上下文
      const canvas = document.getElementById("canvas");
      const ctx = canvas.getContext("2d");

      // 存储点和提示框数据
      let points = [];
      let showLabels = true;

      // 提示框位置类型
      const TOOLTIP_POSITIONS = {
        TOP: 0,
        BOTTOM: 1,
        LEFT: 2,
        RIGHT: 3,
      };

      // 提示框样式配置
      const TOOLTIP_CONFIG = {
        width: 100,
        height: 40,
        padding: 5,
        backgroundColor: "rgba(255, 255, 255, 0.9)",
        borderColor: "#333",
        borderWidth: 1,
        textColor: "#333",
        textSize: 12,
        arrowSize: 8,
      };

      // 生成随机点
      document.getElementById("randomPoints").addEventListener("click", () => {
        generateRandomPoints(30);
        render();
      });

      // 优化布局
      document
        .getElementById("optimizeLayout")
        .addEventListener("click", () => {
          optimizeLayout();
          render();
        });

      // 切换标签显示/隐藏
      document.getElementById("toggleLabels").addEventListener("click", () => {
        showLabels = !showLabels;
        render();
      });

      // 生成随机点
      function generateRandomPoints(count) {
        points = [];
        for (let i = 0; i < count; i++) {
          points.push({
            x: 50 + Math.random() * (canvas.width - 100),
            y: 50 + Math.random() * (canvas.height - 100),
            tooltipPosition: Math.floor(Math.random() * 4), // 随机初始位置
            id: i,
          });
        }
      }

      // 计算提示框的边界框
      function getTooltipBounds(point) {
        const { x, y, tooltipPosition } = point;
        const { width, height, arrowSize } = TOOLTIP_CONFIG;

        switch (tooltipPosition) {
          case TOOLTIP_POSITIONS.TOP:
            return {
              left: x - width / 2,
              top: y - height - arrowSize,
              right: x + width / 2,
              bottom: y - arrowSize,
            };
          case TOOLTIP_POSITIONS.BOTTOM:
            return {
              left: x - width / 2,
              top: y + arrowSize,
              right: x + width / 2,
              bottom: y + height + arrowSize,
            };
          case TOOLTIP_POSITIONS.LEFT:
            return {
              left: x - width - arrowSize,
              top: y - height / 2,
              right: x - arrowSize,
              bottom: y + height / 2,
            };
          case TOOLTIP_POSITIONS.RIGHT:
            return {
              left: x + arrowSize,
              top: y - height / 2,
              right: x + width + arrowSize,
              bottom: y + height / 2,
            };
        }
      }

      // 检测两个边界框是否重叠
      function checkOverlap(rect1, rect2) {
        return (
          rect1.left < rect2.right &&
          rect1.right > rect2.left &&
          rect1.top < rect2.bottom &&
          rect1.bottom > rect2.top
        );
      }

      // 计算当前布局的总重叠数
      function calculateOverlapCount() {
        let count = 0;
        for (let i = 0; i < points.length; i++) {
          const rect1 = getTooltipBounds(points[i]);
          for (let j = i + 1; j < points.length; j++) {
            const rect2 = getTooltipBounds(points[j]);
            if (checkOverlap(rect1, rect2)) {
              count++;
            }
          }
        }
        return count;
      }

      // 优化布局算法
      function optimizeLayout() {
        // 迭代次数初始化
        let iteration = 0;
        // 最大迭代次数，防止死循环
        let maxIterations = 100;
        // 当前重叠数，初始为当前布局的重叠数
        let overlapCount = calculateOverlapCount();
        // 上一次的重叠数，用于判断是否有改进
        let lastOverlapCount = Infinity;

        // 模拟退火算法的初始温度
        let temperature = 100;
        // 温度衰减系数，每次迭代后温度降低
        let coolingRate = 0.95;

        // 只要未达到最大迭代次数且仍有重叠就继续优化
        while (iteration < maxIterations && overlapCount > 0) {
          // 遍历每一个点，尝试为其选择最优的tooltip位置
          for (let i = 0; i < points.length; i++) {
            // 记录当前点的原始位置
            const originalPosition = points[i].tooltipPosition;
            // 初始化最优位置为当前点位置
            let bestPosition = originalPosition;
            // 初始化最小重叠数为当前重叠数
            let minOverlap = overlapCount;

            // 尝试该点的所有可能的tooltip位置（假设有4个位置）
            for (let pos = 0; pos < 4; pos++) {
              // 设置当前尝试的位置
              points[i].tooltipPosition = pos;
              // 计算此时的重叠数
              const newOverlap = calculateOverlapCount();

              // 模拟退火思想：
              // 如果新重叠数更小，直接接受；
              // 如果更大，则以一定概率接受（概率随温度降低而降低），以跳出局部最优
              const delta = newOverlap - minOverlap;
              if (delta < 0 || Math.random() < Math.exp(-delta / temperature)) {
                minOverlap = newOverlap;
                bestPosition = pos;
              }
            }

            // 将该点的tooltip位置设置为本轮最优位置
            points[i].tooltipPosition = bestPosition;
            // 更新全局重叠数为本轮最小重叠数
            overlapCount = minOverlap;
          }

          // 降低温度，逐步减少接受较差解的概率
          temperature *= coolingRate;

          // 更新统计信息到页面
          iteration++;
          document.getElementById(
            "iterations"
          ).textContent = `迭代次数: ${iteration}`;
          document.getElementById(
            "overlapCount"
          ).textContent = `重叠数: ${overlapCount}`;

          // 如果本轮没有改进，提前结束优化
          if (overlapCount === lastOverlapCount) {
            break;
          }
          // 记录本轮的重叠数，供下轮判断
          lastOverlapCount = overlapCount;
        }

        // 返回最终的重叠数
        return overlapCount;
      }

      // 渲染Canvas
      function render() {
        // 清空画布
        ctx.clearRect(0, 0, canvas.width, canvas.height);

        // 绘制所有点和提示框
        points.forEach(point => {
          // 绘制点
          ctx.beginPath();
          ctx.arc(point.x, point.y, 5, 0, Math.PI * 2);
          ctx.fillStyle = "#3498db";
          ctx.fill();
          ctx.closePath();

          // 绘制点ID
          ctx.fillStyle = "#333";
          ctx.font = "12px Arial";
          ctx.fillText(point.id.toString(), point.x + 10, point.y + 5);

          // 如果显示标签，则绘制提示框
          if (showLabels) {
            drawTooltip(point);
          }
        });

        // 更新重叠统计
        const overlapCount = calculateOverlapCount();
        document.getElementById(
          "overlapCount"
        ).textContent = `重叠数: ${overlapCount}`;
      }

      // 绘制提示框
      function drawTooltip(point) {
        const { x, y, tooltipPosition, id } = point;
        const {
          width,
          height,
          padding,
          backgroundColor,
          borderColor,
          borderWidth,
          textColor,
          textSize,
          arrowSize,
        } = TOOLTIP_CONFIG;

        let tooltipX, tooltipY;

        // 根据位置类型计算提示框位置
        switch (tooltipPosition) {
          case TOOLTIP_POSITIONS.TOP:
            tooltipX = x - width / 2;
            tooltipY = y - height - arrowSize;
            break;
          case TOOLTIP_POSITIONS.BOTTOM:
            tooltipX = x - width / 2;
            tooltipY = y + arrowSize;
            break;
          case TOOLTIP_POSITIONS.LEFT:
            tooltipX = x - width - arrowSize;
            tooltipY = y - height / 2;
            break;
          case TOOLTIP_POSITIONS.RIGHT:
            tooltipX = x + arrowSize;
            tooltipY = y - height / 2;
            break;
        }

        // 绘制提示框背景
        ctx.fillStyle = backgroundColor;
        ctx.fillRect(tooltipX, tooltipY, width, height);

        // 绘制提示框边框
        ctx.strokeStyle = borderColor;
        ctx.lineWidth = borderWidth;
        ctx.strokeRect(tooltipX, tooltipY, width, height);

        // 绘制箭头
        ctx.beginPath();
        switch (tooltipPosition) {
          case TOOLTIP_POSITIONS.TOP:
            ctx.moveTo(x, y - arrowSize);
            ctx.lineTo(x - arrowSize, y);
            ctx.lineTo(x + arrowSize, y);
            break;
          case TOOLTIP_POSITIONS.BOTTOM:
            ctx.moveTo(x, y + arrowSize);
            ctx.lineTo(x - arrowSize, y);
            ctx.lineTo(x + arrowSize, y);
            break;
          case TOOLTIP_POSITIONS.LEFT:
            ctx.moveTo(x - arrowSize, y);
            ctx.lineTo(x, y - arrowSize);
            ctx.lineTo(x, y + arrowSize);
            break;
          case TOOLTIP_POSITIONS.RIGHT:
            ctx.moveTo(x + arrowSize, y);
            ctx.lineTo(x, y - arrowSize);
            ctx.lineTo(x, y + arrowSize);
            break;
        }
        ctx.closePath();
        ctx.fillStyle = backgroundColor;
        ctx.fill();
        ctx.strokeStyle = borderColor;
        ctx.stroke();

        // 绘制提示框文本
        ctx.fillStyle = textColor;
        ctx.font = `${textSize}px Arial`;
        ctx.textAlign = "center";
        ctx.textBaseline = "middle";
        ctx.fillText(
          `点 ${id} - 位置 ${tooltipPosition}`,
          tooltipX + width / 2,
          tooltipY + height / 2
        );
      }

      // 初始化
      generateRandomPoints(30);
      render();
    </script>
  </body>
</html>
